package graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * create by yongli on 2020-02-09 11:18
 * 有向图,使用泛型.就相当于设计一个图容器
 * 写代码时，心中要有一设计蓝图
 * 以图中索引来标识一个节点。
 */

public class MyGraph<T> {

    //节点数量
    int num;
    T[] nodes;  //一索引来标识各个节点。
    int[] a = new int[10];
    // ArrayList<T>[]  toList = new ArrayList[10]; 应为这个带有泛型吗？
    List[] toList;  // 每一个元素都是list
    List[] fromList;

    /**
     *
     * @param num 节点数量，提供了两种初始化图的方式
     */
    public MyGraph(int num){
        this.num =num;
        toList = new ArrayList[num-1];
        fromList = new ArrayList[num-1];
        for(int i = 0;i<num;i++){
            toList[i] = new ArrayList<Integer>();
            fromList[i] = new ArrayList<Integer>();
        }
    }

    public MyGraph(T[] nodes){
        this.nodes = nodes;
        int num = nodes.length;
        toList = new ArrayList[num-1];
        fromList = new ArrayList[num-1];
        for(int i = 0;i<num;i++){
            toList[i] = new ArrayList<Integer>();
            fromList[i] = new ArrayList<Integer>();
        }
    }

    /**
     *
     * @param i 删掉该节点，但是不方便补位，设置为null
     * @return
     */


    public boolean delete(int i){
        nodes[i] = null;
        toList[i] = new ArrayList();
        fromList[i] = new ArrayList(); //皆为空，否则还要判断null.
        for(int j =0;j<num;++j){
            //检查一遍,去掉该元素。
            toList[j].remove(i);
            fromList[j].remove(i);
        }
        return true;
    }

    public T getNode(int i){
        return nodes[i]; // i为非法时没有定义.
    }

    public boolean addNode(int i,T node){
        nodes[i] = node; // 可能后期发现设计有问题，如果遇到问题在修改.
        return true;
    }

    // 图中的节点.
    public boolean addEdge(int from,int to){
        if(from < num && to <num && from != to){
            toList[from].add(to);
            return true;
        }else{
            return false;
        }
    }

    public boolean hasPathTo(int i, int j){
        return toList[i].contains(j);
    }

    /**
     *
     * @param i i节点，
     * @param j j节点
     * @return 返回i到j的所有路径
     * 路径查找，可能要用迪杰特斯拉算法
     */
    public List<List<Integer>> pathTo(int i,int j){
        //这个实例化的方式
        List<List<Integer>> paths = new ArrayList<>();
        //返回直连的，如果是非直连，则要一定的搜索方式.bfs;
        if(toList[i].contains(j)){
            List<Integer> path= new ArrayList<>();
            path.add(i);
            path.add(j);
            paths.add(path);
        }


        return paths;
    }

    /**
     *
     * @param paths
     * @param path
     * @param i
     * @param j
     * 前提是这里不存在环。
     */
    private void BFS(List<List<Integer>> paths, Stack<Integer> path, int i, int j){
        if(path.contains(j)){
            List<Integer> path2 = new ArrayList<>(path);
            paths.add(path2);
            return;
        }
        path.push(i);
        //
        for(Object num:toList[i]){
            int n =(Integer)num;
            BFS(paths,path,n,j);
        }
        path.pop();
    }

}

